DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2023.8

Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Authors: Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract

We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.

Cite as

Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
  author =	{Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8},
  URN =		{urn:nbn:de:0030-drops-183585},
  doi =		{10.4230/LIPIcs.SEA.2023.8},
  annote =	{Keywords: sorting, algorithms, randomization, experimentation}
}

Search Results

Documents authored by Dillencourt, Michael

Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Abstract

Cite as

Thanks for your feedback!

Could not send message